/*
合并有序链表
连接：https://leetcode.cn/problems/merge-two-sorted-lists/description/
题目：21. 合并两个有序链表
简介：

两种做法，递归和迭代
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
       if(list1==nullptr)
            return list2;
        if(list2==nullptr)
            return list1;
       if(list1->val<list2->val)
       {
           list1->next = mergeTwoLists(list1->next,list2);
           return list1;
       }
       else
       {
           list2->next = mergeTwoLists(list1,list2->next);
           return list2;
       }
    }
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* cur1=list1;
        ListNode* cur2 = list2;
        ListNode* newroot=new ListNode;
        ListNode* tail = newroot;
        while(cur1!=nullptr && cur2!=nullptr)
        {
            ListNode* last1 = cur1->next;
            ListNode* last2 = cur2->next;
            if(cur1->val<cur2->val)
            {
                tail->next = cur1;
                cur1 = last1;
                tail = tail->next;
            }
            else
            {
                tail->next = cur2;
                cur2 = last2;
                tail = tail->next;
            }
        }
        if(cur1!=nullptr)
        {
            tail->next = cur1;
        }
        else if(cur2!=nullptr)
        {
            tail->next = cur2;
        }
        tail = newroot->next;;
        delete newroot;
        return tail;
    }
};